package randomthoughts.dp;

/**LeetCode:279
 * @author tongchen
 * @create 2023-04-18 11:17
 */
public class PerfectSquare {
    public static void main(String[] args) {

    }

    /**
     * 五部曲：1.dp[i]代表组成i的最小个数；i代表数字；2.递推公式：dp[i]=min(dp[i],dp[i-nums[i]]+1)3.初始化dp[0]=0.dp[i]=max4.遍历顺序：从前往后
     * @param n
     * @return
     */
    public static int askSquare(int n){
        //创建dp数组
        int[]dp=new int[n+1];
        //初始化
        for(int i=1;i<=n;++i){
            dp[i]=Integer.MAX_VALUE;
        }
        //遍历
        for (int i = 1; i*i <=n ; i++) {
            for(int j=i*i;j<=n;++j){
                dp[j]=Math.min(dp[j],dp[j-i*i]+1);
            }
        }
        return dp[n];
    }
}
